class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


def partition_list(head, val):
    dum1 = ListNode(0)
    dum2 = ListNode(1)
    h1 = dum1
    h2 = dum2
    cur = head
    while cur:
        if cur.val < val:
            h1.next = cur
            h1 = h1.next
        else:
            h2.next = cur
            h2 = h2.next
        cur = cur.next

    h2.next = None
    h1.next = dum2

    return dum1.next
